package com.lun.swordtowardoffer2.c13;

import java.util.ArrayList;
import java.util.List;

public class RestoreIpAddress {

	public List<String> restoreIpAddress(String ipAddressSrc){
		List<String> result = new ArrayList<>();
		backstracking(ipAddressSrc, 0, 0, "", result);
		return result;
	}
	
	private void backstracking(String ipAddressSrc, int startIndex, int dotNum, //
				 String ipStr,  List<String> result) {

		if(dotNum == 3) {
			String tempPart = ipAddressSrc.substring(startIndex);
			if(isValidPart(tempPart)) {
				result.add(ipStr + tempPart); 
			}
			return;
		}
		
		String part = "";
		for(int i = startIndex; i < ipAddressSrc.length(); i++) {
			part += ipAddressSrc.charAt(i);
			if(!isValidPart(part)) {
				break;
			}
			backstracking(ipAddressSrc, i + 1, dotNum + 1, ipStr + part + ".", result);
		}
	}
	
	private boolean isValidPart(String str) {		
		return str.matches("\\d|[1-9]\\d|1\\d{2}|2[0-4]\\d|25[0-5]");
	}
	
}
